<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>排序算法 | SunMoon Space</title><meta name="keywords" content="排序"><meta name="author" content="Sun Moon"><meta name="copyright" content="Sun Moon"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="一、简单排序借鉴jdk的形式，在设计算法结构之前，先设计一套API，在对其方法一一实现。  1.1 Comparable接口介绍java开发中，常比较两个java对象。Comparable接口用来定义排序规则，我们对其进行实现即可。 可以对所有实现Comparable接口的对象进行排序。 例如：定义一个类User，实现Comparable接口，定义比较规则；定义测试类，并定义测试方法：Compa">
<meta property="og:type" content="article">
<meta property="og:title" content="排序算法">
<meta property="og:url" content="https://www.sunmoon.site/2021/01/29/%E7%AE%97%E6%B3%95/%E6%8E%92%E5%BA%8F/index.html">
<meta property="og:site_name" content="SunMoon Space">
<meta property="og:description" content="一、简单排序借鉴jdk的形式，在设计算法结构之前，先设计一套API，在对其方法一一实现。  1.1 Comparable接口介绍java开发中，常比较两个java对象。Comparable接口用来定义排序规则，我们对其进行实现即可。 可以对所有实现Comparable接口的对象进行排序。 例如：定义一个类User，实现Comparable接口，定义比较规则；定义测试类，并定义测试方法：Compa">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://s1.ax1x.com/2022/05/19/OHAQQP.jpg">
<meta property="article:published_time" content="2021-01-28T16:37:00.000Z">
<meta property="article:modified_time" content="2022-09-17T00:50:44.773Z">
<meta property="article:author" content="Sun Moon">
<meta property="article:tag" content="排序">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://s1.ax1x.com/2022/05/19/OHAQQP.jpg"><link rel="shortcut icon" href="/img/avatar.jpg"><link rel="canonical" href="https://www.sunmoon.site/2021/01/29/%E7%AE%97%E6%B3%95/%E6%8E%92%E5%BA%8F/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@6/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":200},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: {"limitCount":50,"languages":{"author":"作者: Sun Moon","link":"链接: ","source":"来源: SunMoon Space","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '排序算法',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2022-09-17 08:50:44'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><link rel="stylesheet" href="/css/backgound.css"><meta name="generator" content="Hexo 5.4.2"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/avatar.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">43</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">25</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">10</div></a></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 链接</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i><span> Link</span></a></li><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/aplayer/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://s1.ax1x.com/2022/05/19/OHAQQP.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">SunMoon Space</a></span><div id="he-plugin-simple"></div><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 链接</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i><span> Link</span></a></li><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/aplayer/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">排序算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-01-28T16:37:00.000Z" title="发表于 2021-01-29 00:37:00">2021-01-29</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2022-09-17T00:50:44.773Z" title="更新于 2022-09-17 08:50:44">2022-09-17</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="排序算法"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvnoR0"><img src="https://s1.ax1x.com/2022/05/21/OvnoR0.png" alt="排序1"></a></p>
<h1 id="一、简单排序"><a href="#一、简单排序" class="headerlink" title="一、简单排序"></a>一、简单排序</h1><p>借鉴jdk的形式，在设计算法结构之前，先设计一套API，在对其方法一一实现。</p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvnqLF"><img src="https://s1.ax1x.com/2022/05/21/OvnqLF.png" alt="OvnqLF.png"></a></p>
<h2 id="1-1-Comparable接口介绍"><a href="#1-1-Comparable接口介绍" class="headerlink" title="1.1 Comparable接口介绍"></a>1.1 Comparable接口介绍</h2><p>java开发中，常比较两个java对象。Comparable接口用来定义排序规则，我们对其进行实现即可。</p>
<p>可以对所有实现Comparable接口的对象进行排序。</p>
<p>例如：定义一个类User，实现Comparable接口，定义比较规则；定义测试类，并定义测试方法：Comparable getMax（Comparable c1,Comparable c2）；</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">publiuc <span class="keyword">class</span> <span class="title class_">User</span> <span class="keyword">implements</span> <span class="title class_">Comparable</span>&#123;</span><br><span class="line">    <span class="type">int</span> age;</span><br><span class="line">    String name;</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">User</span><span class="params">()</span>&#123;&#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">User</span><span class="params">(<span class="type">int</span> age,String name)</span>&#123;</span><br><span class="line">        <span class="built_in">this</span>.age=age;</span><br><span class="line">        <span class="built_in">this</span>.name=name;</span><br><span class="line">       </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">this</span>.name+<span class="string">&quot;+&quot;</span>+<span class="built_in">this</span>.age;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">compareTo</span><span class="params">(User u)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">this</span>.age-u.age;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test</span>()&#123;</span><br><span class="line">   <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">()</span>&#123;</span><br><span class="line">   User u1=<span class="keyword">new</span> <span class="title class_">User</span>(<span class="number">20</span>,<span class="string">&quot;zhangsan&quot;</span>);</span><br><span class="line">   User u2=<span class="keyword">new</span> <span class="title class_">User</span>(<span class="number">15</span>,<span class="string">&quot;lisi&quot;</span>);</span><br><span class="line">   Comparable max=getMax(u1,u2);<span class="comment">//多态</span></span><br><span class="line">   System.out.println(max);</span><br><span class="line">   &#125;</span><br><span class="line">   <span class="keyword">public</span> <span class="keyword">static</span> Comparable <span class="title function_">getMax</span><span class="params">(Comparable c1,Comparable c2)</span>&#123;</span><br><span class="line">       <span class="type">int</span> result=c1.compareTo(c2);</span><br><span class="line">       <span class="keyword">if</span>(result&gt;=<span class="number">0</span>)&#123;</span><br><span class="line">       <span class="keyword">return</span> c1;</span><br><span class="line">       &#125;<span class="keyword">else</span></span><br><span class="line">       <span class="keyword">return</span> c2;</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1-2冒泡排序（Bubble-sort）"><a href="#1-2冒泡排序（Bubble-sort）" class="headerlink" title="1.2冒泡排序（Bubble sort）"></a>1.2冒泡排序（Bubble sort）</h2><h3 id="1-2-1-原理"><a href="#1-2-1-原理" class="headerlink" title="1.2.1 原理"></a>1.2.1 原理</h3><ol>
<li>比较相邻元素。如果前一个大就交换两元素位置。</li>
<li>最终从小到大排序。</li>
<li>进行   <strong>数组长度-1</strong>   次大循环</li>
<li><strong>优化：</strong> <strong><u>某次循环中若没有发生交换，则已经有序，直接结束剩下的次数。</u></strong></li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/Ovupz6"><img src="https://s1.ax1x.com/2022/05/21/Ovupz6.png" alt="Ovupz6.png"></a></p>
<p>（这里实际冒泡5次，长度-1次）</p>
<h3 id="1-2-2-API设计"><a href="#1-2-2-API设计" class="headerlink" title="1.2.2 API设计"></a>1.2.2 API设计</h3><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Bubble</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Bubble()</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void exch(Comparable[] a, int i, int j);   交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2</td>
</tr>
</tbody></table>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">package</span> BubbleSort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Bubble</span> &#123;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 数组排序</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> arr 进行排序的数组，需要是引用数据类型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span><span class="params">(Comparable[] arr)</span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i=arr.length-<span class="number">1</span>; i&gt;<span class="number">0</span>; i--)    <span class="comment">//大循环次数（冒泡次数）：长度-1次，尽量用索引表示</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j=<span class="number">0</span>; j&lt;i; j++)&#123;        <span class="comment">//每次循环比较的次数，尽量用索引表示</span></span><br><span class="line">                <span class="keyword">if</span> (greater(arr[j],arr[j+<span class="number">1</span>]))&#123;</span><br><span class="line">                    exch(arr,j,j+<span class="number">1</span>);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 比较数组中的两个元素</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> c1 第一个元素</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> c2 第二个元素</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 第一个大于第二个，true；否则false</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">greater</span><span class="params">(Comparable c1,Comparable c2)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> c1.compareTo(c2)&gt;<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 交换数组中的索引i和索引j上的元素</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组a，存储的元素要求为引用类型</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> i 索引i</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> j 索引j</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">exch</span><span class="params">(Comparable[] a,<span class="type">int</span> i, <span class="type">int</span> j)</span>&#123;</span><br><span class="line">        Comparable temp;</span><br><span class="line">        temp=a[i];</span><br><span class="line">        a[i]=a[j];</span><br><span class="line">        a[j]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="1-2-3-时间复杂度"><a href="#1-2-3-时间复杂度" class="headerlink" title="1.2.3 时间复杂度"></a>1.2.3 时间复杂度</h3><p>O（n^2）   因此，待排序数较少时候可以，当数量较大时候，效率较低。</p>
<h3 id="1-2-4-写到一块-优化"><a href="#1-2-4-写到一块-优化" class="headerlink" title="1.2.4 写到一块+优化"></a>1.2.4 写到一块+优化</h3><figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package BubbleSort;</span><br><span class="line"></span><br><span class="line">import java.util.Arrays;</span><br><span class="line"></span><br><span class="line">public class Bubble01 &#123;</span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        Comparable[] a=&#123;1,5,3,45&#125;;  //integer实现了Comparable，多态</span><br><span class="line">        for (int i=a.length-1; i&gt;0; i--)&#123;</span><br><span class="line">           </span><br><span class="line">           boolean exchRight=false;//建立标志，看是否发生交换</span><br><span class="line">            </span><br><span class="line">            for (int j=0; j&lt; i; j++)&#123;</span><br><span class="line">                if (a[j].compareTo(a[j+1])&gt;0)&#123;</span><br><span class="line">                    Comparable temp=a[j];</span><br><span class="line">                    a[j]=a[j+1];</span><br><span class="line">                    a[j+1]=temp;</span><br><span class="line">                    //发生了交换</span><br><span class="line">                    exchRight=true;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            //检测本次循环中是否发生交换</span><br><span class="line">            //没发生交换则结束循环</span><br><span class="line">            if (!exchRight)&#123;</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(Arrays.toString(a));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1-3选择排序（Selection-sort）"><a href="#1-3选择排序（Selection-sort）" class="headerlink" title="1.3选择排序（Selection sort）"></a>1.3选择排序（Selection sort）</h2><h3 id="1-3-1-原理"><a href="#1-3-1-原理" class="headerlink" title="1.3.1 原理"></a>1.3.1 原理</h3><ol>
<li>（为每个位置找最小值）假设第一个索引为：    <strong>最小值索引</strong>   ，进行比较，  **找出最小索引 ** 。</li>
<li>**交换 ** 第一个索引处的值和最小值所在索引处的值。</li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/Ovukee"><img src="https://s1.ax1x.com/2022/05/21/Ovukee.png" alt="Ovukee.png"></a></p>
<h3 id="1-3-2-API设计"><a href="#1-3-2-API设计" class="headerlink" title="1.3.2 API设计"></a>1.3.2 API设计</h3><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Selection</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Bubble()</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void exch(Comparable[] a, int i, int j);   交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2</td>
</tr>
</tbody></table>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package selectSort;</span><br><span class="line"></span><br><span class="line">public class Selection &#123;</span><br><span class="line">    public static void sort(Comparable[] arr)&#123;</span><br><span class="line">        for (int i=0;i&lt;arr.length-1; i++)&#123;</span><br><span class="line">        //记录最小元素的索引值，初始认为是参与选择排序的第一个位置。</span><br><span class="line">            int min=i;</span><br><span class="line">            for (int j=i+1; j&lt;arr.length; j++)&#123;</span><br><span class="line">            //比较最小索引处的值和j索引处的值</span><br><span class="line">                if (greater(arr[min],arr[j]))&#123;</span><br><span class="line">                    min=j;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            if (min!=i)&#123;</span><br><span class="line">                exch(arr,i,min);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">  //比较两个元素</span><br><span class="line">    private static boolean greater(Comparable c1,Comparable c2)&#123;</span><br><span class="line">        return c1.compareTo(c2)&gt;0;</span><br><span class="line">    &#125;</span><br><span class="line">  //交换两个索引位的元素</span><br><span class="line">    private static void exch(Comparable[] arr,int i, int j)&#123;</span><br><span class="line">        Comparable temp=arr[i];</span><br><span class="line">        arr[i]=arr[j];</span><br><span class="line">        arr[j]=temp;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="1-3-3-时间复杂度"><a href="#1-3-3-时间复杂度" class="headerlink" title="1.3.3 时间复杂度"></a>1.3.3 时间复杂度</h3><p>O（n^2）   因此，待排序数较少时候可以，当数量较大时候，效率较低。</p>
<h3 id="1-3-4-写到一块"><a href="#1-3-4-写到一块" class="headerlink" title="1.3.4 写到一块"></a>1.3.4 写到一块</h3><figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">//写到一块的算法</span><br><span class="line">package selectSort;</span><br><span class="line"></span><br><span class="line">import java.util.Arrays;</span><br><span class="line"></span><br><span class="line">public class Selection_01 &#123;</span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        Comparable[] a=&#123;454,85,1,0,9,5&#125;;</span><br><span class="line">        //从索引为0的位置找最小值，最后一个索引位不需要找，一共循环length-1次。</span><br><span class="line">        for (int i=0;i&lt;a.length-1;i++)&#123;</span><br><span class="line">            //保存最小元素下标</span><br><span class="line">            int min=i;</span><br><span class="line">            //将元素与剩下元素进行比较，找出最小元素的下标</span><br><span class="line">            for (int nextIndex=i+1;nextIndex&lt;a.length;nextIndex++)&#123;</span><br><span class="line">                if (a[min].compareTo(a[nextIndex])&gt;0)&#123;</span><br><span class="line">                    min=nextIndex;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            //每大循环一次，检测a[i]的值是否是最小的</span><br><span class="line">            if (min !=i)&#123;</span><br><span class="line">                Comparable temp=a[i];</span><br><span class="line">                a[i]=a[min];</span><br><span class="line">                a[min]=temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(Arrays.toString(a));</span><br><span class="line">     &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1-4插入排序（Insertion-sort）"><a href="#1-4插入排序（Insertion-sort）" class="headerlink" title="1.4插入排序（Insertion sort）"></a>1.4插入排序（Insertion sort）</h2><h3 id="1-4-1-原理"><a href="#1-4-1-原理" class="headerlink" title="1.4.1 原理"></a>1.4.1 原理</h3><ol>
<li>元素分组：已排序，未排序。</li>
<li>未排序第一个元素向已排序组中插入。</li>
<li>倒叙遍历已排序元素，依次和待插入元素比较，若待插元素小，<strong>交换</strong>。直到找到一个元素小于等于待插元素，停止交换，即插入成功。<br><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvueJI"><img src="https://s1.ax1x.com/2022/05/21/OvueJI.png" alt="OvueJI.png"></a></li>
</ol>
<h3 id="1-4-2-API设计"><a href="#1-4-2-API设计" class="headerlink" title="1.4.2 API设计"></a>1.4.2 API设计</h3><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Insertion</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Insertion()</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void exch(Comparable[] a, int i, int j);   交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2</td>
</tr>
</tbody></table>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package InsertionSort;</span><br><span class="line"></span><br><span class="line">public class Insertion &#123;</span><br><span class="line">    public static void sort(Comparable[] arr)&#123;</span><br><span class="line">//待插入元素的索引</span><br><span class="line">        for (int i=1; i&lt;arr.length; i++)&#123;  //第一组已排序数组</span><br><span class="line"></span><br><span class="line">            for (int j=i; j&gt;0; j--)&#123;   //已排序元素倒叙遍历</span><br><span class="line">                if (greater(arr[j-1],arr[j]))&#123;</span><br><span class="line">                    exch(arr,j-1,j);</span><br><span class="line">                &#125;</span><br><span class="line">                else break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    private static boolean greater(Comparable c1,Comparable c2)&#123;</span><br><span class="line">        return c1.compareTo(c2)&gt;0;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    private static void exch(Comparable[] arr, int i,int j)&#123;</span><br><span class="line">        Comparable temp=arr[i];</span><br><span class="line">        arr[i]=arr[j];</span><br><span class="line">        arr[j]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="1-4-5-时间复杂度"><a href="#1-4-5-时间复杂度" class="headerlink" title="1.4.5 时间复杂度"></a>1.4.5 时间复杂度</h3><p>O（n^2）   因此，待排序数较少时候可以，当数量较大时候，效率较低。</p>
<h3 id="1-4-6-写到一块"><a href="#1-4-6-写到一块" class="headerlink" title="1.4.6 写到一块"></a>1.4.6 写到一块</h3><figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package InsertionSort;</span><br><span class="line"></span><br><span class="line">import java.util.Arrays;</span><br><span class="line"></span><br><span class="line">public class Insertion01 &#123;</span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        Comparable[] arr=&#123;4,3,2,10,12,1,5,6&#125;;</span><br><span class="line">        //找到待插入元素的索引</span><br><span class="line">        for (int i=1;i&lt;arr.length;i++)&#123;</span><br><span class="line">            //倒序遍历已排序数组，两两比较，前面大时就交换，前面不大时说明当前待插入元素已经有序，终止遍历</span><br><span class="line">            //将待比较元素放在有序组的最后一位，在这个组中从后往前，两两比较。</span><br><span class="line">            for (int j=i;j&gt;0;j--)&#123;  //这里的j也可以认为是待插入元素</span><br><span class="line">                if (arr[j-1].compareTo(arr[j])&gt;0)&#123;</span><br><span class="line">                   Comparable temp=arr[j-1];</span><br><span class="line">                   arr[j-1]=arr[j];</span><br><span class="line">                   arr[j]=temp;</span><br><span class="line">                &#125;</span><br><span class="line">                else break;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(Arrays.toString(arr));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="二、高级排序"><a href="#二、高级排序" class="headerlink" title="二、高级排序"></a>二、高级排序</h1><p>简单排序的时间复杂度均为O（n^2），随这输入规模的增大，时间将急剧上升，不能处理大规模问题。</p>
<h2 id="2-1希尔排序（Shell-Sort）"><a href="#2-1希尔排序（Shell-Sort）" class="headerlink" title="2.1希尔排序（Shell Sort）"></a>2.1希尔排序（Shell Sort）</h2><h3 id="2-1-1-原理（插入排序的改良）"><a href="#2-1-1-原理（插入排序的改良）" class="headerlink" title="2.1.1 原理（插入排序的改良）"></a>2.1.1 原理（插入排序的改良）</h3><ol>
<li><p>选定增长量h,按照h进行数组分组（h组数据）。</p>
</li>
<li><p>每一组数组完成    <u><strong>直接插入排序</strong></u>。</p>
</li>
<li><p>减小增长量，重复第2步，直到增长量为1。</p>
</li>
<li><p>增长量h没有固定原则，以下是一种：</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">int h=1;</span><br><span class="line">while(h&lt;length/2)&#123;</span><br><span class="line">    h=2h+1;   //初始h大于二分之一个数组长度</span><br><span class="line">&#125;</span><br><span class="line">//循环后h的减小规则</span><br><span class="line">     h=h/2</span><br></pre></td></tr></table></figure></li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvuuSP"><img src="https://s1.ax1x.com/2022/05/21/OvuuSP.png" alt="OvuuSP.png"></a></p>
<h3 id="2-1-2-API设计"><a href="#2-1-2-API设计" class="headerlink" title="2.1.2 API设计"></a>2.1.2 API设计</h3><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Shell</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Shell()；创建Shell对象</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void exch(Comparable[] a, int i, int j);   交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2</td>
</tr>
</tbody></table>
<figure class="highlight javascript"><table><tr><td class="code"><pre><span class="line">package <span class="title class_">ShellSort</span>;</span><br><span class="line"></span><br><span class="line">public <span class="keyword">class</span> <span class="title class_">Shell</span> &#123;</span><br><span class="line">    public <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span>(<span class="params">Comparable[] arr</span>)&#123;</span><br><span class="line">        <span class="comment">//1.根据数组长度确定初始h</span></span><br><span class="line">        int h=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (h&lt;arr.<span class="property">length</span>/<span class="number">2</span>)&#123;</span><br><span class="line">            h=<span class="number">2</span>*h+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//2.希尔排序</span></span><br><span class="line">        <span class="keyword">while</span>(h&gt;=<span class="number">1</span>)&#123;</span><br><span class="line">          <span class="comment">//排序</span></span><br><span class="line"></span><br><span class="line">            <span class="comment">//2.1 找到每个待插入元素</span></span><br><span class="line">            <span class="keyword">for</span> (int i=h;i&lt;arr.<span class="property">length</span>;i++)&#123;</span><br><span class="line">                <span class="comment">//2.2 把待插入元素插入到有序数组中</span></span><br><span class="line">                <span class="comment">//倒叙遍历有序数组,没组数据中的元素下标之间相差h</span></span><br><span class="line">                <span class="keyword">for</span> (int j=i; j&gt;=h; j-=h)&#123;</span><br><span class="line"></span><br><span class="line">                    <span class="comment">//待插入元素a[j]，a[j-h]</span></span><br><span class="line">                    <span class="keyword">if</span> (<span class="title function_">greater</span>(arr[j-h],arr[j]))&#123;</span><br><span class="line">                        <span class="title function_">exch</span>(arr,j-h,j);</span><br><span class="line">                    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                        <span class="comment">//待插入元素已经找到合适位置</span></span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">          <span class="comment">//减小h的值</span></span><br><span class="line">          h=h/<span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/*下面代码可以替换上面的while</span></span><br><span class="line"><span class="comment">        for (;h&gt;0;h/=2)&#123;</span></span><br><span class="line"><span class="comment">            for ()</span></span><br><span class="line"><span class="comment">                if (greater(arr[]))</span></span><br><span class="line"><span class="comment">        &#125;*/</span></span><br><span class="line">    &#125;</span><br><span class="line">    private <span class="keyword">static</span> boolean <span class="title function_">greater</span>(<span class="params">Comparable c1,Comparable c2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> c1.<span class="title function_">compareTo</span>(c2)&gt;<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    private <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">exch</span>(<span class="params">Comparable[] arr,int i, int j</span>)&#123;</span><br><span class="line">        <span class="title class_">Comparable</span> temp=arr[i];</span><br><span class="line">        arr[i]=arr[j];</span><br><span class="line">        arr[j]=temp;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-1-3-时间复杂度"><a href="#2-1-3-时间复杂度" class="headerlink" title="2.1.3 时间复杂度"></a>2.1.3 时间复杂度</h3><p>采用事后时间分析，对比直接插入排序，效率提高了很多。</p>
<h3 id="2-1-4-写到一块"><a href="#2-1-4-写到一块" class="headerlink" title="2.1.4 写到一块"></a>2.1.4 写到一块</h3><figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package ShellSort;</span><br><span class="line"></span><br><span class="line">import java.util.Arrays;</span><br><span class="line"></span><br><span class="line">public class Shell01 &#123;</span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">       Comparable[] arr=&#123;5,2,78,4,1,0&#125;;</span><br><span class="line">        int h=1;</span><br><span class="line">        while (h&lt;arr.length/2)&#123;</span><br><span class="line">            h=h*2+1;</span><br><span class="line">        &#125;</span><br><span class="line">        while (h&gt;=1)&#123;</span><br><span class="line">            //找到待插入元素</span><br><span class="line">            for (int i=h; i&lt;arr.length; i++)&#123;</span><br><span class="line">                //倒叙遍历有序数组进行插入</span><br><span class="line">                for (int j=i; j&gt;=h; j-=h)&#123;</span><br><span class="line">                    if (arr[j-h].compareTo(arr[j])&gt;0)&#123;</span><br><span class="line">                        Comparable temp=arr[j-h];</span><br><span class="line">                        arr[j-h]=arr[j];</span><br><span class="line">                        arr[j]=temp;</span><br><span class="line">                    &#125;else &#123;</span><br><span class="line">                        //前面的比后面的小，说明已经有序</span><br><span class="line">                        break;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            h=h/2;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(Arrays.toString(arr));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="2-2归并排序"><a href="#2-2归并排序" class="headerlink" title="2.2归并排序"></a>2.2归并排序</h2><h3 id="2-2-1递归"><a href="#2-2-1递归" class="headerlink" title="2.2.1递归"></a>2.2.1递归</h3><p><strong>定义：</strong>方法内部调用方法本身。</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">public void show()&#123;</span><br><span class="line">    sout(&quot;dfdf&quot;);</span><br><span class="line">    show();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>作用：</strong>将大型复杂真题转换成与原问题相似的小规模问题求解，用少量程序描述多次重复计算。</p>
<p><strong>注意：</strong>不能无限制调用自己，应该设置边界条件，防止发生栈溢出（每调用一次，栈中开辟一块空间）。</p>
<p>例如：用代码实现n的阶乘。</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">package MergeSort;</span><br><span class="line"></span><br><span class="line">public class n_jie &#123;</span><br><span class="line">    public static void main(String[] args) &#123;</span><br><span class="line">        System.out.println(jie(19));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    public static int jie(int n)&#123;</span><br><span class="line">        //终止条件一般写在返回结果前面</span><br><span class="line">        if (n==1||n==0)&#123;</span><br><span class="line">            return 1;</span><br><span class="line">        &#125;</span><br><span class="line">        return n*jie(n-1);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-2-2归并排序（Merge-Sort）"><a href="#2-2-2归并排序（Merge-Sort）" class="headerlink" title="2.2.2归并排序（Merge Sort）"></a>2.2.2归并排序（Merge Sort）</h3><p>分治法的典型应用，将已有序的子序列合并。</p>
<h4 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h4><ol>
<li>将数组等额拆分，直到每个组仅有一个元素为止。</li>
<li>相邻自组合并，直到最终仅有一个组为止（边合并边排序，归并后的元素要有序）。</li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvuMy8"><img src="https://s1.ax1x.com/2022/05/21/OvuMy8.png" alt="排序7"></a></p>
<p>3.归并原理：将归并后的数据放在辅助数组，通过3个数组来完成。比较上面两指针的元素，将较小的放在辅助数组中，并且被放的元素的指针后移。</p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvuYYn"><img src="https://s1.ax1x.com/2022/05/21/OvuYYn.png" alt="OvuYYn.png"></a></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvuUS0"><img src="https://s1.ax1x.com/2022/05/21/OvuUS0.png" alt="OvuUS0.png"></a></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvK9ts"><img src="https://s1.ax1x.com/2022/05/21/OvK9ts.png" alt="排序10"></a></p>
<h4 id="API设计"><a href="#API设计" class="headerlink" title="API设计"></a>API设计</h4><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Merge</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Merge()</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void exch(Comparable[] a, int i, int j);   没有用到。交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2private static void sort（Comparable[] a, int lo, int hi）；对数组中索引lo到hi的元素进行排序private static void merge(Comparable[] a, int lo, int mid, int hi);索引lo到mid为有一个自组；mid+1到hi为另外一个自组。将a的两个子组合并为有序的大组。</td>
</tr>
<tr>
<td>成员变量</td>
<td align="left">private static Comparable[] assist;完成归并操作的辅助数组</td>
</tr>
</tbody></table>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">package</span> MergeSort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Merge</span> &#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> Comparable[] assist;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">greater</span><span class="params">(Comparable c1 , Comparable c2)</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> c1.compareTo(c2)&gt;<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span><span class="params">(Comparable[] a)</span>&#123;</span><br><span class="line">        <span class="comment">//1.初始化辅助数组</span></span><br><span class="line">        assist=<span class="keyword">new</span> <span class="title class_">Comparable</span>[a.length];</span><br><span class="line"></span><br><span class="line">        <span class="comment">//2.定义一个lo变量，hi变量。记录数组中的最小索引和最大索引</span></span><br><span class="line">        <span class="type">int</span> lo=<span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> hi=a.length-<span class="number">1</span>;</span><br><span class="line">        <span class="comment">//3.调用sort重载方法完成数组a中，从lo到hi索引处的排序</span></span><br><span class="line">       sort(a,lo,hi);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//用了递归</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span><span class="params">(Comparable[] a,<span class="type">int</span> lo,<span class="type">int</span> hi)</span>&#123;</span><br><span class="line">        <span class="comment">//做安全性检查</span></span><br><span class="line">        <span class="keyword">if</span> (hi&lt;=lo)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//对lo和hi之间的数据进行分组</span></span><br><span class="line">        <span class="type">int</span> mid=lo+(hi-lo)/<span class="number">2</span>;</span><br><span class="line">        <span class="comment">//对每一组中的数据进行排序</span></span><br><span class="line">        sort(a,lo,mid);</span><br><span class="line">        sort(a,mid+<span class="number">1</span>,hi);</span><br><span class="line">        <span class="comment">//将两组数据进行归并</span></span><br><span class="line">        merge(a,lo,mid,hi);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 对两组数据进行归并，边归并边进行排序</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> lo 数组开始索引</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> mid 数组中间元素索引</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> hi 数组结束索引</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">merge</span><span class="params">(Comparable[] a,<span class="type">int</span> lo, <span class="type">int</span> mid, <span class="type">int</span> hi)</span>&#123;</span><br><span class="line">       <span class="comment">//定义三个指针</span></span><br><span class="line">        <span class="type">int</span> p1=lo;</span><br><span class="line">        <span class="type">int</span> p2=mid+<span class="number">1</span>;</span><br><span class="line">        <span class="type">int</span> p3=lo;   <span class="comment">//这里容易错，注意辅助数组的开始下标</span></span><br><span class="line">        <span class="comment">//遍历移动p1p2指针，找出小的放在辅助数组对应的位置</span></span><br><span class="line">        <span class="comment">//当其中一个分组遍历结束时，就结束遍历</span></span><br><span class="line">        <span class="keyword">while</span> (p1&lt;=mid &amp;&amp; p2&lt;=hi)&#123;</span><br><span class="line">            <span class="keyword">if</span> (greater(a[p1],a[p2]))&#123;</span><br><span class="line">                assist[p3++]=a[p2++];</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                assist[p3++]=a[p1++];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//放元素过程结束后，其中的一个子数组的元素可能还没有放完，接着放剩下</span></span><br><span class="line">        <span class="comment">//p1指针没有走完的情况</span></span><br><span class="line">        <span class="keyword">while</span> (p1&lt;=mid)&#123;</span><br><span class="line">            assist[p3++]=a[p1++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//p2指针没有走完的情况</span></span><br><span class="line">        <span class="keyword">while</span>(p2&lt;=hi)&#123;</span><br><span class="line">            assist[p3++]=a[p2++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//遍历把辅助数组的元素copy到原来数组</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> index=lo; index&lt;=hi; index++)&#123;</span><br><span class="line">            a[index]=assist[index];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//辅助数组</span></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span>[] temp;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span>[] sortArray(<span class="type">int</span>[] nums) &#123;</span><br><span class="line">        <span class="built_in">this</span>.temp = <span class="keyword">new</span> <span class="title class_">int</span>[nums.length];</span><br><span class="line">        subSort(nums, <span class="number">0</span>, nums.length-<span class="number">1</span>);</span><br><span class="line">        <span class="keyword">return</span> nums;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//递归分为两个子问题</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">subSort</span><span class="params">(<span class="type">int</span>[] nums, <span class="type">int</span> l, <span class="type">int</span> r)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(l &gt;= r )&#123;</span><br><span class="line">            <span class="keyword">return</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (l + r)/<span class="number">2</span>;</span><br><span class="line">        subSort(nums, l, mid);</span><br><span class="line">        subSort(nums, mid+<span class="number">1</span>, r);</span><br><span class="line">        mertTwoSortedArr(nums, l, r, mid);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//解决子问题，并归并</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">mertTwoSortedArr</span><span class="params">(<span class="type">int</span>[] nums, <span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> mid)</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">left</span> <span class="operator">=</span> l;</span><br><span class="line">        <span class="type">int</span> <span class="variable">right</span> <span class="operator">=</span> mid+<span class="number">1</span>;</span><br><span class="line">        <span class="type">int</span> <span class="variable">fIndex</span> <span class="operator">=</span> left;<span class="comment">//辅助数组的开始索引</span></span><br><span class="line">        <span class="keyword">while</span>(left &lt;= mid &amp;&amp; right &lt;= r)&#123;</span><br><span class="line">            <span class="keyword">if</span>(nums[left] &lt;= nums[right])&#123;</span><br><span class="line">                temp[fIndex++] = nums[left++];</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                temp[fIndex++] = nums[right++];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(left &lt;= mid)&#123;</span><br><span class="line">            temp[fIndex++] = nums[left++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(right &lt;= r)&#123;</span><br><span class="line">            temp[fIndex++] = nums[right++];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//辅助数组中的元素放回原来数组</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=l; i&lt;=r; i++)&#123;</span><br><span class="line">            nums[i] = temp[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<h4 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h4><p>O（nlogn） 效率较高。</p>
<p>缺点：需要申请额外的数组空间，空间复杂度提升，典型的空间换时间的操作。</p>
<h4 id="希尔排序和归并排序比较"><a href="#希尔排序和归并排序比较" class="headerlink" title="希尔排序和归并排序比较"></a>希尔排序和归并排序比较</h4><p>通过事后分析。二则的效率差不多，要根据算法的稳定性进行抉择。</p>
<h2 id="2-3快速排序"><a href="#2-3快速排序" class="headerlink" title="2.3快速排序"></a>2.3快速排序</h2><h3 id="2-3-1-原理（插入排序的改良）"><a href="#2-3-1-原理（插入排序的改良）" class="headerlink" title="2.3.1 原理（插入排序的改良）"></a>2.3.1 原理（插入排序的改良）</h3><ol>
<li>设定分界值，将数组分为左右两部分。</li>
<li>大于等于分界值的放在右边，小于的放在左边。</li>
<li>对于左右数组重复步骤2.</li>
<li>将递归排序后的数组进行合并。</li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvKVnU"><img src="https://s1.ax1x.com/2022/05/21/OvKVnU.png" alt="OvKVnU.png"></a></p>
<p>切分原理：</p>
<ol>
<li><p>确定基准值（数组第一个），用两个指针分别指向头部和尾部的下一位。</p>
</li>
<li><p>先从尾部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；</p>
</li>
<li><p>再从头部像尾部搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；</p>
</li>
<li><p>交换当前左右边指针上的元素。</p>
</li>
<li><p>重复上步骤，直到left&gt;&#x3D;right。</p>
</li>
<li><p>交换基准值和当前两指针指向的元素。</p>
<p><strong>注意：</strong>当切分不充分时候，分界值左边的元素：<strong>小于等于分界值</strong>；分界值右边的元素：<strong>大于等于分界值</strong>。</p>
</li>
</ol>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvKe74"><img src="https://s1.ax1x.com/2022/05/21/OvKe74.png" alt="OvKe74.png"></a></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvK1c6"><img src="https://s1.ax1x.com/2022/05/21/OvK1c6.png" alt="13"></a></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvKGnO"><img src="https://s1.ax1x.com/2022/05/21/OvKGnO.png" alt="14"></a></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvKa4A"><img src="https://s1.ax1x.com/2022/05/21/OvKa4A.png" alt="OvKa4A.png"></a></p>
<h3 id="2-3-2-API设计"><a href="#2-3-2-API设计" class="headerlink" title="2.3.2 API设计"></a>2.3.2 API设计</h3><table>
<thead>
<tr>
<th>类名</th>
<th align="left">Quick</th>
</tr>
</thead>
<tbody><tr>
<td>构造方法</td>
<td align="left">Quick()；创建Shell对象</td>
</tr>
<tr>
<td>成员方法</td>
<td align="left">public static void sort(Comparable[] a); 对数组内的元素进行排序private static void sort(Comparable[] a, int lo. int hi); 对数组中的部分元素进行排序 private static int partion (Comparable[] a ,int lo,int hi); 对数组a中索引lo到hi的元素进行分组，并返回分界索引值。private static void exch(Comparable[] a, int i, int j);   交换数组a中索引 i 和 j 的值private static boolean greater(Comparable c1，Comparable c2);  判断c1是否大于c2</td>
</tr>
</tbody></table>
<figure class="highlight javascript"><table><tr><td class="code"><pre><span class="line">package <span class="title class_">Quick</span>;</span><br><span class="line"></span><br><span class="line">public <span class="keyword">class</span> <span class="title class_">Quick</span> &#123;</span><br><span class="line">    public <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span>(<span class="params">Comparable[] a</span>)&#123;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//1.定义一个lo变量，hi变量。记录数组中的最小索引和最大索引</span></span><br><span class="line">        int lo=<span class="number">0</span>;</span><br><span class="line">        int hi=a.<span class="property">length</span>-<span class="number">1</span>;</span><br><span class="line">        <span class="title function_">sort</span>(a,lo,hi);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//用了递归</span></span><br><span class="line">    private <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span>(<span class="params">Comparable[] a,int lo,int hi</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (hi&lt;=lo)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//数组中lo到hi的元素进行分组</span></span><br><span class="line">        int partion=<span class="title function_">partion</span>(a,lo,hi);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//让左子组有序</span></span><br><span class="line">        <span class="title function_">sort</span>(a,lo,partion-<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//让右子组有序</span></span><br><span class="line">        <span class="title function_">sort</span>(a,partion+<span class="number">1</span>,hi);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 对数组a中，从索引lo到hi的元素进行分组，并反会分组界限对应的索引</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> <span class="variable">a</span></span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> <span class="variable">lo</span></span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> <span class="variable">hi</span></span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 分组界限值对应的索引。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    private <span class="keyword">static</span> int <span class="title function_">partion</span>(<span class="params">Comparable[] a,int lo, int hi</span>)&#123;</span><br><span class="line"></span><br><span class="line">       int left=lo;</span><br><span class="line">       int right=hi+<span class="number">1</span>;</span><br><span class="line">       <span class="keyword">while</span> (<span class="literal">true</span>)&#123;</span><br><span class="line">           <span class="comment">//先从右往左扫，右指针指向一个 小于等于 基准值的元素</span></span><br><span class="line">           <span class="keyword">while</span> (<span class="title function_">greater</span>(a[--right],a[lo]))&#123;</span><br><span class="line">               <span class="keyword">if</span> (right==lo)&#123;</span><br><span class="line">                   <span class="keyword">break</span>;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="comment">//左指针找到一个  大于等于  基准值的元素</span></span><br><span class="line">           <span class="keyword">while</span> (<span class="title function_">greater</span>(a[lo],a[++left]))&#123;</span><br><span class="line">               <span class="keyword">if</span> (left==hi)&#123;<span class="comment">//左指针移动到最右边时候要结束</span></span><br><span class="line">                   <span class="keyword">break</span>;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="keyword">if</span> (left&gt;=right)&#123;<span class="comment">//扫描完所有元素，结束循环</span></span><br><span class="line">               <span class="keyword">break</span>;</span><br><span class="line">           &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">               <span class="comment">//交换左右指针上的元素</span></span><br><span class="line">               <span class="title function_">exch</span>(a,left,right);</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="comment">//交换分界值,注意要和right指针上的交换，因为有可能right指针可能在left指针的左边，但right上的元数一般比left上的元素小，要保证将较小的元素放到最左边。</span></span><br><span class="line">       <span class="title function_">exch</span>(a,lo,right);</span><br><span class="line">        <span class="keyword">return</span> right;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    private <span class="keyword">static</span> boolean <span class="title function_">greater</span>(<span class="params">Comparable c1,Comparable c2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> c1.<span class="title function_">compareTo</span>(c2)&gt;<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    private <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">exch</span>(<span class="params">Comparable[] a, int i,int j</span>)&#123;</span><br><span class="line">        <span class="title class_">Comparable</span> temp=a[i];</span><br><span class="line">        a[i]=a[j];</span><br><span class="line">        a[j]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">int</span>[] sortArray(<span class="type">int</span>[] nums) &#123;</span><br><span class="line">        subSort(nums, <span class="number">0</span>, nums.length-<span class="number">1</span>);</span><br><span class="line">        <span class="keyword">return</span> nums;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//递归</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">subSort</span><span class="params">(<span class="type">int</span>[] nums, <span class="type">int</span> l, <span class="type">int</span> r)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(l &gt;= r)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> <span class="variable">portion</span> <span class="operator">=</span> portion(nums, l, r);</span><br><span class="line">        subSort(nums, l, portion - <span class="number">1</span>);</span><br><span class="line">        subSort(nums, portion + <span class="number">1</span> , r);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//分组（进行交换排序），并返回界限的索引</span></span><br><span class="line">    <span class="comment">//将一个数组按数组中的一个数poration分为两部分，前面的都</span></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> <span class="title function_">portion</span><span class="params">(<span class="type">int</span>[] nums, <span class="type">int</span> l, <span class="type">int</span> r)</span>&#123;</span><br><span class="line">        <span class="comment">//随机找数组中一个数  与第一个数交换，作为分界值poration</span></span><br><span class="line">        <span class="comment">//防止遇见完全递增的序列，每次划分都将数组分为‘1’个子数组，尽量避免O（n^2）时间复杂度</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">randomIndex</span> <span class="operator">=</span> l + <span class="keyword">new</span> <span class="title class_">Random</span>().nextInt(r-l+<span class="number">1</span>);</span><br><span class="line">        exch(nums, randomIndex, l);</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span> <span class="variable">portionNum</span> <span class="operator">=</span> nums[l];</span><br><span class="line">        <span class="comment">//两个指针找大于poration和小于poration的数</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">left</span> <span class="operator">=</span> l;</span><br><span class="line">        <span class="type">int</span> <span class="variable">right</span> <span class="operator">=</span> r;</span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="comment">//右指针找到第一个比portion小的数</span></span><br><span class="line">            <span class="keyword">while</span>(right &gt; l &amp;&amp; nums[right] &gt;= portionNum) right--;</span><br><span class="line">            <span class="comment">//左指针找到第一比portion大的数</span></span><br><span class="line">            <span class="keyword">while</span> (left &lt;= r &amp;&amp; nums[left] &lt;= portionNum) left++;</span><br><span class="line">            <span class="comment">//找到了两个数了，左指针是否在右指针左边，在的话交换</span></span><br><span class="line">            <span class="keyword">if</span>(left &lt; right)&#123;</span><br><span class="line">                exch(nums, left, right);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//寻找结束，</span></span><br><span class="line">        exch(nums, l, right);</span><br><span class="line">        <span class="keyword">return</span> right;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">exch</span><span class="params">(<span class="type">int</span>[] nums, <span class="type">int</span> fist, <span class="type">int</span> second)</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> nums[fist];</span><br><span class="line">        nums[fist] = nums[second];</span><br><span class="line">        nums[second] = temp;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<h3 id="2-3-3-时间复杂度"><a href="#2-3-3-时间复杂度" class="headerlink" title="2.3.3 时间复杂度"></a>2.3.3 时间复杂度</h3><p>快速排序一次切分从两头开始交替搜素，直到left和right重合，因此，一次切分算法的时间复杂度为O（n），整个时间复杂度取决于切分次数。</p>
<p><strong>最优情况：</strong>每一次切分选择的基准数子刚好将当前序列等分。</p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/OvKDjf"><img src="https://s1.ax1x.com/2022/05/21/OvKDjf.png" alt="16"></a></p>
<p>上图共切分logn此，所以最优情况下：<strong>O(nlogn)</strong></p>
<p><strong>最坏情况：</strong>每一次选择的基准数字是当前序列的最大数或最小数，每次切分都只有1个子组，那么一共切割n次，因此最坏情况：<strong>O(n^2)</strong></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/Ov8fC4"><img src="https://s1.ax1x.com/2022/05/21/Ov8fC4.png" alt="Ov8fC4.png"></a></p>
<p><strong>平均情况：</strong>O（nlogn）</p>
<h3 id="2-3-4快速排序和归并排序的区别"><a href="#2-3-4快速排序和归并排序的区别" class="headerlink" title="2.3.4快速排序和归并排序的区别"></a>2.3.4快速排序和归并排序的区别</h3><p>相同：都是分治算法</p>
<p>区别：</p>
<ol>
<li>归并排序将数组分成两个数组分别排序，将有序的子数组归并；快速排序是当两个数组有序时，整个数组就有序，无需归并。</li>
<li>切分：归并排序是根据lo和hi等分两半；而快速排序切分的位置取决于数组内容；</li>
</ol>
<h2 id="2-4排序的稳定性"><a href="#2-4排序的稳定性" class="headerlink" title="2.4排序的稳定性"></a>2.4排序的稳定性</h2><h3 id="稳定性"><a href="#稳定性" class="headerlink" title="稳定性"></a><strong>稳定性</strong></h3><p><strong>相等元素的相对位置不发生变化，则稳定。</strong></p>
<p><a target="_blank" rel="noopener" href="https://imgtu.com/i/Ov8h8J"><img src="https://s1.ax1x.com/2022/05/21/Ov8h8J.png" alt="Ov8h8J.png"></a></p>
<h3 id="意义"><a href="#意义" class="headerlink" title="**意义 **"></a>**意义 **</h3><p>仅针对多次排序的情况来说。<strong>保证第一次排序的原有意义，并减少系统开销。</strong>例如：第一次排序按照商品价格排序，第二次按照销量排序，对于销量相同的产品，其相对位置不发生变动，则之前按照价格排序的意义就可以保持不变。</p>
<h3 id="几种算法的稳定性"><a href="#几种算法的稳定性" class="headerlink" title="几种算法的稳定性"></a><strong>几种算法的稳定性</strong></h3><p>稳定：冒泡排序、插入排序、归并排序</p>
<p>不稳定：选择排序、希尔排序、快速排序</p>
<h2 id="2-5堆排序"><a href="#2-5堆排序" class="headerlink" title="2.5堆排序"></a>2.5堆排序</h2><h3 id="2-5-1-应用了堆的相关原理，具体见堆哪一章"><a href="#2-5-1-应用了堆的相关原理，具体见堆哪一章" class="headerlink" title="2.5.1 应用了堆的相关原理，具体见堆哪一章"></a>2.5.1 应用了堆的相关原理，具体见堆哪一章</h3><p><a href="https://www.sunmoon.site/2021/05/01/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%A0%86/">堆 | SunMoon Space</a></p>
<h1 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h1><p>时间复杂度：nlogn</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">PriorityQueue&lt;Integer&gt; pq = <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;&gt;();<span class="comment">//小顶堆（默认）</span></span><br><span class="line">PriorityQueue&lt;Integer&gt; pq = <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;&gt;((x,y)-&gt;y-x);<span class="comment">//大顶堆</span></span><br></pre></td></tr></table></figure>

<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/submissions/">703. 数据流中的第 K 大元素 - 力扣（LeetCode） (leetcode-cn.com)</a></p>
<p>采用小顶堆，使堆中只包含<strong>k个最大的元素</strong>，最后顶部是第k大的元素。</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">class KthLargest &#123;</span><br><span class="line">    private PriorityQueue&lt;Integer&gt; pq ;</span><br><span class="line">    private int k;</span><br><span class="line">    public KthLargest(int k, int[] nums) &#123;</span><br><span class="line">        this.pq = new PriorityQueue&lt;&gt;();</span><br><span class="line">        for (int i=0; i&lt;nums.length; i++)&#123;</span><br><span class="line">            pq.offer(nums[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        this.k = k;</span><br><span class="line">    &#125;</span><br><span class="line">    public int add(int val) &#123;</span><br><span class="line">        pq.offer(val);</span><br><span class="line">        while (pq.size() &gt; k)&#123;</span><br><span class="line">            pq.poll();</span><br><span class="line">        &#125;</span><br><span class="line">        return pq.peek();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/kth-largest-element-in-an-array/">215. 数组中的第K个最大元素 - 力扣（LeetCode） (leetcode-cn.com)</a></p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Sun Moon</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://www.sunmoon.site/2021/01/29/%E7%AE%97%E6%B3%95/%E6%8E%92%E5%BA%8F/">https://www.sunmoon.site/2021/01/29/%E7%AE%97%E6%B3%95/%E6%8E%92%E5%BA%8F/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://www.sunmoon.site" target="_blank">SunMoon Space</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E6%8E%92%E5%BA%8F/">排序</a></div><div class="post_share"><div class="social-share" data-image="https://s1.ax1x.com/2022/05/19/OHAQQP.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src="/img/wechat.jpg" alt="wechat"/></a><div class="post-qr-code-desc">wechat</div></li><li class="reward-item"><a href="/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src="/img/alipay.jpg" alt="alipay"/></a><div class="post-qr-code-desc">alipay</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2021/01/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88/"><img class="prev-cover" src="https://s1.ax1x.com/2022/05/19/OHAVde.md.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">双指针</div></div></a></div><div class="next-post pull-right"><a href="/2021/01/29/%E7%AE%97%E6%B3%95/%E9%80%92%E5%BD%92%E5%9B%9E%E6%BA%AF/"><img class="next-cover" src="https://s1.ax1x.com/2022/05/19/OHApGR.md.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">递归、回溯</div></div></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/img/avatar.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">Sun Moon</div><div class="author-info__description">Hi, welcome to my blog!</div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">43</div></a></div><div class="card-info-data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">25</div></a></div><div class="card-info-data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">10</div></a></div></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/sun-moon22"><i class="fab fa-github"></i><span>关注我</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/sun-moon22" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="https://qm.qq.com/cgi-bin/qm/qr?k=zftgTJPReW-aEsUnWx6dKFfD03rovP8a&amp;noverify=0" target="_blank" title="QQ"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">欢迎来到我的博客！</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E7%AE%80%E5%8D%95%E6%8E%92%E5%BA%8F"><span class="toc-number">1.</span> <span class="toc-text">一、简单排序</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-1-Comparable%E6%8E%A5%E5%8F%A3%E4%BB%8B%E7%BB%8D"><span class="toc-number">1.1.</span> <span class="toc-text">1.1 Comparable接口介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-2%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%EF%BC%88Bubble-sort%EF%BC%89"><span class="toc-number">1.2.</span> <span class="toc-text">1.2冒泡排序（Bubble sort）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-1-%E5%8E%9F%E7%90%86"><span class="toc-number">1.2.1.</span> <span class="toc-text">1.2.1 原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-2-API%E8%AE%BE%E8%AE%A1"><span class="toc-number">1.2.2.</span> <span class="toc-text">1.2.2 API设计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-3-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.2.3.</span> <span class="toc-text">1.2.3 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-4-%E5%86%99%E5%88%B0%E4%B8%80%E5%9D%97-%E4%BC%98%E5%8C%96"><span class="toc-number">1.2.4.</span> <span class="toc-text">1.2.4 写到一块+优化</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-3%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%EF%BC%88Selection-sort%EF%BC%89"><span class="toc-number">1.3.</span> <span class="toc-text">1.3选择排序（Selection sort）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-1-%E5%8E%9F%E7%90%86"><span class="toc-number">1.3.1.</span> <span class="toc-text">1.3.1 原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-2-API%E8%AE%BE%E8%AE%A1"><span class="toc-number">1.3.2.</span> <span class="toc-text">1.3.2 API设计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-3-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.3.3.</span> <span class="toc-text">1.3.3 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-4-%E5%86%99%E5%88%B0%E4%B8%80%E5%9D%97"><span class="toc-number">1.3.4.</span> <span class="toc-text">1.3.4 写到一块</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-4%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%EF%BC%88Insertion-sort%EF%BC%89"><span class="toc-number">1.4.</span> <span class="toc-text">1.4插入排序（Insertion sort）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-1-%E5%8E%9F%E7%90%86"><span class="toc-number">1.4.1.</span> <span class="toc-text">1.4.1 原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-2-API%E8%AE%BE%E8%AE%A1"><span class="toc-number">1.4.2.</span> <span class="toc-text">1.4.2 API设计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-5-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.4.3.</span> <span class="toc-text">1.4.5 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-6-%E5%86%99%E5%88%B0%E4%B8%80%E5%9D%97"><span class="toc-number">1.4.4.</span> <span class="toc-text">1.4.6 写到一块</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E9%AB%98%E7%BA%A7%E6%8E%92%E5%BA%8F"><span class="toc-number">2.</span> <span class="toc-text">二、高级排序</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#2-1%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%EF%BC%88Shell-Sort%EF%BC%89"><span class="toc-number">2.1.</span> <span class="toc-text">2.1希尔排序（Shell Sort）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-1-%E5%8E%9F%E7%90%86%EF%BC%88%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%9A%84%E6%94%B9%E8%89%AF%EF%BC%89"><span class="toc-number">2.1.1.</span> <span class="toc-text">2.1.1 原理（插入排序的改良）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-2-API%E8%AE%BE%E8%AE%A1"><span class="toc-number">2.1.2.</span> <span class="toc-text">2.1.2 API设计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-3-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.1.3.</span> <span class="toc-text">2.1.3 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-4-%E5%86%99%E5%88%B0%E4%B8%80%E5%9D%97"><span class="toc-number">2.1.4.</span> <span class="toc-text">2.1.4 写到一块</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-2%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">2.2.</span> <span class="toc-text">2.2归并排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-1%E9%80%92%E5%BD%92"><span class="toc-number">2.2.1.</span> <span class="toc-text">2.2.1递归</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-2%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%EF%BC%88Merge-Sort%EF%BC%89"><span class="toc-number">2.2.2.</span> <span class="toc-text">2.2.2归并排序（Merge Sort）</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8E%9F%E7%90%86"><span class="toc-number">2.2.2.1.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#API%E8%AE%BE%E8%AE%A1"><span class="toc-number">2.2.2.2.</span> <span class="toc-text">API设计</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.2.2.3.</span> <span class="toc-text">时间复杂度</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E6%AF%94%E8%BE%83"><span class="toc-number">2.2.2.4.</span> <span class="toc-text">希尔排序和归并排序比较</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-3%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-number">2.3.</span> <span class="toc-text">2.3快速排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-1-%E5%8E%9F%E7%90%86%EF%BC%88%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E7%9A%84%E6%94%B9%E8%89%AF%EF%BC%89"><span class="toc-number">2.3.1.</span> <span class="toc-text">2.3.1 原理（插入排序的改良）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-2-API%E8%AE%BE%E8%AE%A1"><span class="toc-number">2.3.2.</span> <span class="toc-text">2.3.2 API设计</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-3-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.3.3.</span> <span class="toc-text">2.3.3 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-4%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E5%92%8C%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-number">2.3.4.</span> <span class="toc-text">2.3.4快速排序和归并排序的区别</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-4%E6%8E%92%E5%BA%8F%E7%9A%84%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">2.4.</span> <span class="toc-text">2.4排序的稳定性</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">2.4.1.</span> <span class="toc-text">稳定性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%84%8F%E4%B9%89"><span class="toc-number">2.4.2.</span> <span class="toc-text">**意义 **</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%87%A0%E7%A7%8D%E7%AE%97%E6%B3%95%E7%9A%84%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">2.4.3.</span> <span class="toc-text">几种算法的稳定性</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-5%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-number">2.5.</span> <span class="toc-text">2.5堆排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-5-1-%E5%BA%94%E7%94%A8%E4%BA%86%E5%A0%86%E7%9A%84%E7%9B%B8%E5%85%B3%E5%8E%9F%E7%90%86%EF%BC%8C%E5%85%B7%E4%BD%93%E8%A7%81%E5%A0%86%E5%93%AA%E4%B8%80%E7%AB%A0"><span class="toc-number">2.5.1.</span> <span class="toc-text">2.5.1 应用了堆的相关原理，具体见堆哪一章</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-number">3.</span> <span class="toc-text">堆排序</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/05/02/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%89%8D%E7%BC%80%E6%95%B0/" title="前缀树"><img src="https://s1.ax1x.com/2022/05/19/OHApGR.md.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="前缀树"/></a><div class="content"><a class="title" href="/2022/05/02/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%89%8D%E7%BC%80%E6%95%B0/" title="前缀树">前缀树</a><time datetime="2022-05-01T16:37:00.000Z" title="发表于 2022-05-02 00:37:00">2022-05-02</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/04/30/%E4%BD%BF%E7%94%A8%E5%BF%85%E8%AF%BB/" title="Ikiler在线 Markdown"><img src="https://s1.ax1x.com/2022/05/19/OHAkqO.md.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Ikiler在线 Markdown"/></a><div class="content"><a class="title" href="/2022/04/30/%E4%BD%BF%E7%94%A8%E5%BF%85%E8%AF%BB/" title="Ikiler在线 Markdown">Ikiler在线 Markdown</a><time datetime="2022-04-29T16:37:00.000Z" title="发表于 2022-04-30 00:37:00">2022-04-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/04/29/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/" title="平衡二叉树"><img src="https://s1.ax1x.com/2022/05/19/OHA9R1.md.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="平衡二叉树"/></a><div class="content"><a class="title" href="/2022/04/29/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/" title="平衡二叉树">平衡二叉树</a><time datetime="2022-04-28T16:37:00.000Z" title="发表于 2022-04-29 00:37:00">2022-04-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/04/29/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%BA%BF%E6%80%A7%E8%A1%A8/" title="线性表"><img src="https://s1.ax1x.com/2022/05/19/OHApGR.md.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="线性表"/></a><div class="content"><a class="title" href="/2022/04/29/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E7%BA%BF%E6%80%A7%E8%A1%A8/" title="线性表">线性表</a><time datetime="2022-04-28T16:37:00.000Z" title="发表于 2022-04-29 00:37:00">2022-04-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/01/29/%E4%BA%92%E8%81%94%E7%BD%91%E7%94%9F%E6%80%81/Docker/" title="docker"><img src="https://s1.ax1x.com/2022/05/19/OHACxx.md.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="docker"/></a><div class="content"><a class="title" href="/2022/01/29/%E4%BA%92%E8%81%94%E7%BD%91%E7%94%9F%E6%80%81/Docker/" title="docker">docker</a><time datetime="2022-01-28T16:37:00.000Z" title="发表于 2022-01-29 00:37:00">2022-01-29</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2023 By Sun Moon</div><div class="footer_custom_text"><a href="https://beian.miit.gov.cn/"  style="color:white" target="_blank">晋ICP备2022004590号-1</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.js"></script><div class="js-pjax"></div><script src="https://widget.qweather.net/simple/static/js/he-simple-common.js?v=2.0"></script><script async src="/js/weather.js"></script><script src="https://myhkw.cn/player/js/jquery.min.js" type="text/javascript"></script><script src="https://myhkw.cn/api/player/1651412271121" id="myhk" key="1651412271121" m="1"></script><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script><script id="click-show-text" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-show-text.min.js" data-mobile="true" data-text="暴帅,暴富,健康,happy" data-fontsize="15px" data-random="true" async="async"></script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/gh/metowolf/MetingJS@1.2/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = ["title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"]

var pjax = new Pjax({
  elements: 'a:not([target="_blank"])',
  selectors: pjaxSelectors,
  cacheBust: false,
  analytics: false,
  scrollRestoration: false
})

document.addEventListener('pjax:send', function () {

  // removeEventListener scroll 
  window.tocScrollFn && window.removeEventListener('scroll', window.tocScrollFn)
  window.scrollCollect && window.removeEventListener('scroll', scrollCollect)

  typeof preloader === 'object' && preloader.initLoading()
  document.getElementById('rightside').style.cssText = "opacity: ''; transform: ''"
  
  if (window.aplayers) {
    for (let i = 0; i < window.aplayers.length; i++) {
      if (!window.aplayers[i].options.fixed) {
        window.aplayers[i].destroy()
      }
    }
  }

  typeof typed === 'object' && typed.destroy()

  //reset readmode
  const $bodyClassList = document.body.classList
  $bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')

})

document.addEventListener('pjax:complete', function () {
  window.refreshFn()

  document.querySelectorAll('script[data-pjax]').forEach(item => {
    const newScript = document.createElement('script')
    const content = item.text || item.textContent || item.innerHTML || ""
    Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
    newScript.appendChild(document.createTextNode(content))
    item.parentNode.replaceChild(newScript, item)
  })

  GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()

  typeof chatBtnFn === 'function' && chatBtnFn()
  typeof panguInit === 'function' && panguInit()

  // google analytics
  typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});

  // baidu analytics
  typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);

  typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()

  // prismjs
  typeof Prism === 'object' && Prism.highlightAll()

  typeof preloader === 'object' && preloader.endLoading()
})

document.addEventListener('pjax:error', (e) => {
  if (e.request.status === 404) {
    pjax.loadUrl('/404.html')
  }
})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>